1. Technical Field
The present invention relates generally to document authentication. More particularly, the present invention relates to the authentication of graphs at the object level as well as the pixel level.
2. Discussion
For as long as humans have communicated with one another, there has been concern over maintaining confidentiality. As a result, verbal, written, and electronic messages have all been the subject of substantial technological efforts to maintain security. For example, document authentication techniques are commonly used to ensure the integrity of a wide variety of electronic documents such as, presentations, contracts, military orders, and databases. Authentication involves the task of making the determination that the document has not been tampered with and that it originated with the presumed transmitter. Authentication using digital watermarks is a particular technique that has been studied by many researchers in the last ten years. For example, digital watermarking has been successfully applied to digital documents such as digital color/gray scale images and plain text. While electronic document authentication efforts have experienced considerable success, it is important to note that these efforts have typically centered around the protection of textual documents and images.
Recently, however, more and more documents are using graphs in addition to images and text for system and idea illustration. In contrast to images, graphs are more difficult to watermark because of low capacity of additive noise. This is due to the binary nature of graphs. The term “binary nature” relates to the fact that most graphs have one bit per pixel, whereas most images have multiple bits per pixel to indicate varying shades and colors. Binary pixels make it particularly hard to insert watermarks due to the low capacity for perceptual invisible noise. In other words, a minimal alteration of bits in a binary graph can result in a substantial change in the appearance and content of the graph. Furthermore, the critical information of a graph is often contained at the object level rather than the pixel level. For example, a useful application for document copying and copyright protection is to provide different levels of access to different users. In such a case it would be very desirable to detect alteration of the original document as well as localize the alteration on the object level. For example, it is more important to detect a substantive change in a document, such as “10%” to “70%”, than it is to detect an increase in the size of an arrow by one pixel. Thus, the sensitive information in a document is often contained on the object level rather than the pixel level.
Pixel level authentication may also result in less flexibility. For example, if the annotation font of a graph changes but the content of the graph does not, pixel level authentication will alert the owner that the annotations have been altered. The owner has no way of determining, however, that the content of the graph matches the original. Object level authentication, on the other hand, would assure the owner that the “content is authentic” in such a case. If the font is marked as sensitive information, object level authentication could also alert the owner to font alterations. In many applications, however, it would be highly desirable to provide a mechanism for returning an “authentic” determination if the font is not marked as sensitive information.
Conventional methodologies for content-based text authentication mainly rely on altering the word/line spacing or the length of character vertical serif strokes. While text documents are often referred to as binary images and share the same binary nature of graphs, these methodologies can hardly be extended to authentication of graphs. This is because even on the pixel level graphs generally do not exhibit the same characteristics as text. For instance, in a graphical flowchart the shape of each node may be very important, whereas the nodes often have substantially fewer characters as compared to a paragraph of text. In such a flowchart the number of objects that exhibit a vertical serif can be as low as a few percent of the total number of objects. Here, an object is referred to an alterable line, character, or curve. In fact, other kinds of graphs may not exhibit alterable line spacing or vertical serif at all. It is therefore desirable to bridge text-based authentication techniques to the authentication of graphs.